package 算法模板;

/**
 *
 */
public class 并查集 {

    public static void main(String[] args) {

    }

    // 经验: 如果有一个格子网格，每个格子可以往上，下，左，右拓展，那么
    // 遍历时，只需要将上，右的格子连接起来，就能将所有连线都遍历到
    static class DisjointSetUnion {

        // pre[0]=1,代表 0 节点的上级节点是 1
        // pre[1]=1,代表 1 是根节点
        private int[] pre;

        // pre[1]=2,代表 1 节点的最大深度是 2
        private int[] rank;

        public DisjointSetUnion(int n) {
            pre = new int[n];
            rank = new int[n];

            for (int i = 0; i < n; i++) {
                // 初始化每个节点都是根节点
                pre[i] = i;
                rank[i] = 1;
            }
        }

        // 查找 x 的根节点
        public int find(int x) {
            if (pre[x] == x) {
                return x;
            }
            return find(pre[x]);
        }

        // 路径压缩优化一，为了降低树的深度，将 x 节点到其根节点路径上的
        // 所有节点，全部变成根节点的下级节点，
        public int findAndUpdate(int x) {
            if (pre[x] == x) {
                return x;
            }
            return pre[x] = findAndUpdate(pre[x]);
        }

        // 合并 x 的根节点，和 y 的根节点
        // 路径压缩优化二(加权标记法)，优先将根节点深度较小的树，挂到深度较大的树下面
        // 具体的，如果 rank(x)<rank(y)?pre[x]=y:pre[y]=x
        public void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;

            if (rank[x] < rank[y]) {
                pre[x] = y;
            } else {
                pre[y] = x;
                // 两颗深度相等的树，合并在一起，深度+1
                if (rank[x] == rank[y]) {
                    rank[x]++;
                }
            }
        }

        // x 和 y 是否连通，即是否是同一个根节点
        public boolean connected(int x, int y) {
            return findAndUpdate(x) == findAndUpdate(y);
        }
    }

}
